package test230607;

import java.util.Arrays;

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * @date 2023/6/7 16:43
 * 646. 最长数对链
 * https://leetcode.cn/problems/maximum-length-of-pair-chain/
 */
public class Solution01 {

     public int findLongestChain(int[][] pairs) {
         // 先对数对排序
         Arrays.sort(pairs, (a, b) -> (a[0] - b[0]));
         int n = pairs.length;
         int[] dp = new int[n];  // dp[i] 表示以 i 位置数对结尾的数对链最大的长度
         // 初始化
         Arrays.fill(dp, 1);
         int maxLen = 1;
         for (int i = 1; i < n; ++i) {
             for (int j = 0; j <= i- 1; ++j) {
                 if (pairs[i][0] > pairs[j][1]) {
                     dp[i] = Math.max(dp[i], dp[j] + 1);
                 }
             }
             maxLen = Math.max(dp[i], maxLen);
         }
         return maxLen;
     }


    // 测试
    public static void main(String[] args) {
        int[][] pairs = {
                {1, 2},
                {2, 3},
                {3, 4}
        };
        int longestChain = new Solution01().findLongestChain(pairs);
        System.out.println(longestChain);
    }
}
